import org.w3c.dom.html.HTMLHeadingElement;

import javax.xml.transform.sax.SAXTransformerFactory;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-09-10
 * Time: 22:25
 */
public class Solution {

    /**
     *  二分查找
     */
    public int findRadius(int[] houses, int[] heaters) {
        int houseLen = houses.length;
        int heatersLen = heaters.length;
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int left = 0;
        int right = Math.max(houses[houseLen-1], heaters[heatersLen-1]) - 1;
        while (left < right) {
            int mid = ((right - left)>>1) + left;
            if (!judge(mid, houses, heaters)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     *  根据房屋的位置及半径判断周围是否有 供暖器
     *  注意是根据房屋判断, 而不是根据供暖器所能供应的范围判断, 因为判断房屋更简洁
     */
    private boolean judge(int radius, int[] houses, int[] heaters) {
        int len = houses.length;
        int heatIndex = 0; // 供暖器的位置, 一直在增加
        int hLen = heaters.length;
        for (int i = 0; i < len; i++) {
            int pos = houses[i];
            int left = pos - radius;
            // 房屋左边但是覆盖不了该房屋的位置一律跳过
            while (heatIndex < hLen && heaters[heatIndex] < left) {
                heatIndex++;
            }
            // 判断是否能真正覆盖
            if (heatIndex == hLen || heaters[heatIndex] > (pos + radius)) {
                return false;
            }
        }
        return true;
    }
}
